package top100.stack;

import java.util.*;

/**
 * @Author ZhangCuirong
 * @Date 2025/7/16 9:14
 * @description: 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 * 示例 1:
 * 输入：heights = [2,1,5,6,2,3]
 * 输出：10
 * 解释：最大的矩形为图中红色区域，面积为 10
 * 示例 2：
 * 输入： heights = [2,4]
 * 输出： 4
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= heights.length <=105
 * 0 <= heights[i] <= 104
 */
public class Solution84 {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int max = 0;
        Map<Integer, Integer[]> map = new HashMap<>();
        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {//右边第一个比他小的
                int top = stack.pop();
                map.put(top, map.getOrDefault(top, new Integer[]{-1, -1}));
                map.get(top)[1] = i;
            }
            stack.push(i);
        }
        stack.clear();
        for (int i = heights.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                int top = stack.pop();
                map.put(top, map.getOrDefault(top, new Integer[]{-1, -1}));
                map.get(top)[0] = i;
            }
            stack.push(i);
        }
        for (int i = 0; i < heights.length; i++) {
            if(map.containsKey(i)){
                int left = map.get(i)[0] == -1 ? 0 : map.get(i)[0] + 1;
                int right = map.get(i)[1] == -1 ? heights.length-1 : map.get(i)[1] - 1;
                max = Math.max(max, (right - left+1) * heights[i]);
            }else{
                max = Math.max(max, heights.length * heights[i]);
            }

        }
        return max;
    }

    public static void main(String[] args) {
        int[] heights = new int[]{2,3};
        System.out.println(new Solution84().largestRectangleArea(heights));

    }
}
